package binary_tree.LeetCode;

/**
 * 在一个二叉树中对于任意两个节点，找出它们的最近公共祖先
 */
public class Num236 {
    //最近公共祖先
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          //在二叉树中的每个节点开始通过后序遍历寻找p和q两个节点
        findNode(root,p,q);
        return lca;
    }
    /**
     * 在当前二叉树中从根节点开始，后序遍历寻找p和q，找到一个后就返回true
     * @param root
     * @param p
     * @param q
     */
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return false;
        }
        //返回1就说明，此时在左子树中至少找到了一个节点
        int left=findNode(root.left,p,q)?1:0;
        //返回1就说明，此时在右子树中至少找到了一个节点
        int right=findNode(root.right,p,q)?1:0;
        //返回1就说明此时根节点至少有一个是要找的节点
        int mid=(root==p||root==q)?1:0;
        //根据分析可以知道，p和q会出现在当前三个位置中的任意两个
        if (left+right+mid==2){
        //当这三个加来等于2时，就说明p和q出现在了当前节点的三个位置的任意两个位置
        //此时root节点必定是最近公共祖先节点
        lca=root;
        }
        //此时说明至少找到了一个节点
        return(left+right+mid)>0;
    }
}
